/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  const n = s.length
  const dp = [];
  for(let i = 0; i <= n - 1; i++) {
    dp[i] = []
  }
  let ans = ''
  for(let l = 1; l <= n; l++) {
    for(let i = 0; i + l <= n; i++) {
      const j = i + l - 1
      if (j === i) {
        dp[i][j] = true
      } else if (i + 1 === j){
        dp[i][j] = s[i] === s[j]
      } else {
        dp[i][j] = dp[i + 1][j - 1] && s[i] === s[j]
      }
      if (dp[i][j] && l > ans.length) {
        ans = s.substring(i, j + 1)
      }
    }
  }
  return ans;
};

console.log(longestPalindrome('babad'))
console.log(longestPalindrome('cbbd'))
console.log(longestPalindrome('ac'))
